package LeetCode.month03.day76;

import java.util.*;

/**
 * @author 16778
 * @date 2025/10/16 16:59
 * @description
 */
public class No133 {
    private Map<Node,Node> visited = new HashMap<>();
    public Node cloneGraphdp(Node node) {
        if(node==null){
            return null;
        }
        if(visited.containsKey(node)){
            return visited.get(node);
        }
        Node cloneNode = new Node(node.val, new ArrayList<>());
        for (Node neighbor : node.neighbors) {
            cloneNode.neighbors.add(cloneGraphdp(neighbor));
        }
        visited.put(node,cloneNode);
        return cloneNode;
    }

    public Node cloneGraphbp(Node node){
        if(node==null) return null;
        Node root = new Node(node.val,new ArrayList<>());
        if(node.neighbors==null || node.neighbors.size()==0) return root;
        Map<Node,Node> visited = new HashMap<>();
        visited.put(node,root);
        Deque<Node> deque = new ArrayDeque<>();
        deque.add(node);
        while(deque.size()>0){
            Node node1 = deque.removeFirst();
            for (Node neighbor : node1.neighbors) {
                if(!visited.containsKey(neighbor)){
                    visited.put(neighbor,new Node(neighbor.val,new ArrayList<>()));
                    deque.add(neighbor);
                }
                visited.get(node1).neighbors.add(visited.get(neighbor));
            }
        }
        return visited.get(node);
    }
}
